package likou.jindian;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/26 10:08
 */
public class _10_09 {
    public static void main(String[] args) {
        System.out.println(searchMatrix(new int[][]{{1,4},{2,5}},5));
    }
    public static boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0){
            return false;
        }
        //确认区间
        int row = matrix.length;
        int col = matrix[0].length;
        return search(matrix,target,new int[]{0,0},new int[]{row-1,col-1});
    }
    public static boolean search(int[][] matrix,int target,int[] start,int[] end){
        if(start[0]>end[0]||start[1]>end[1]){
            return false;
        }
        //找到对角线上刚好比它大的那个元素。
        int sI = start[0],sJ=start[1];
        int eI = end[0],eJ=end[1];
        int deep = Math.min(eI-sI,eJ-sJ);
//        if (deep==0){//说明此时需要遍历的是一条直线！
//            if (eI==sI){
//                while (sJ<=eJ){
//                    if (matrix[sI][sJ]==target){
//                        return true;
//                    }
//                    sJ++;
//                }
//            }else {
//                while (sI<=eI){
//                    if (matrix[sI][sJ]==target){
//                        return true;
//                    }
//                    sI++;
//                }
//            }
//            return false;
//        }
        while(deep>=0){
            if(matrix[sI][sJ]==target) return true;
            if(matrix[sI][sJ]>target){
                break;
            }
            sI++;sJ++;
            deep--;
        }
        if(matrix[--sI][--sJ]>target){//说明接下来查找区间为左下部分，和右上部分
            return search(matrix,target,new int[]{sI,start[1]},new int[]{end[0],sJ-1})||search(matrix,target,new int[]{start[0],sJ},new int[]{sI-1,end[1]});
        }else{
            //此时查找区间为下方部分，或者右方部分
            if(sI==end[0]){//查找右边部分
                return search(matrix,target,new int[]{start[0],sJ+1},new int[]{end[0],end[1]});
            }else{//查找下方部分
                return search(matrix,target,new int[]{sI+1,start[1]},new int[]{end[0],end[1]});
            }
        }
    }
}
